using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;

using FineCollection.Intf;




namespace FineCollection.Bits
{
    
    /// <summary>
    /// Set of integers where each integers existence 
    /// stores as a correspondent bit,
    /// with fixed lower bound.
    /// </summary>
    public class BitIntSet : RSet<int>
    {
        /// <summary>
        /// Number relates the first bit in the <see cref="bits"/> array.
        /// Initially is 0.
        /// </summary>
        internal readonly int origin;

        /// <summary>
        /// Array of bits.
        /// </summary>
        private ulong[] bits;

        /// <summary>
        /// Count of items in the set, that is equivalent of how many bits are "1".
        /// </summary>
        private int count;


        /// <summary>
        /// The first item.
        /// </summary>
        /// <remarks>
        /// Valid only if the set is not empty.
        /// </remarks>
        private int first;

        /// <summary>
        /// The last item.
        /// </summary>
        /// <remarks>
        /// Valid only if the set is not empty.
        /// </remarks>
        private int last;


        /// <summary>
        /// Sequence number for iterator.
        /// This number is incremented each time the collection is changed.
        /// </summary>
        internal uint sequenceNr;


        /// <summary>
        /// Constructs a set, with zero origin.
        /// </summary>
        /// <seealso cref="BitIntSet(int)"/>
        public BitIntSet()
            : this(0)
        {}

        
        /// <summary>
        /// Constructs a set.
        /// </summary>
        /// <param name="origin">the minimal integer value that this set will operate with.</param>
        public BitIntSet(int origin)
        {
            this.origin = origin;
            Clear();
        }

        
        /// <summary>
        /// Includes the given item.
        /// </summary>
        /// <param name="item">item to include.</param>
        public void Include(int item)
        {
            if (item < origin)
                throw new ArgumentException("BitIntSet: the given argument (" + item +
                                            ") is less that the container origin (" +
                                            origin + ").");

            uint wordNr;
            ulong word, mask;
            CalculateWordAndMask(item, out wordNr, out word, out mask);

            if (bits == null || wordNr >= bits.Length)
                ExpandBits(wordNr+1);

            // change the bit if needed
            if ((word & mask) == 0)
            {
                bits[wordNr] |= mask;
                count++;
                sequenceNr++;
            }
            else
            {
                return;
            }

            // update first and last
            if (count == 1)
            {
                first = last = item;
            }
            else
            {
                if (item < first) first = item;
                if (item > last)  last = item;
            }
        }


        /// <summary>
        /// Excludes the given item.
        /// </summary>
        /// <param name="item">item to exclude.</param>
        public void Exclude(int item)
        {
            if (item < origin)
                return;

            uint wordNr;
            ulong word, mask;
            CalculateWordAndMask(item, out wordNr, out word, out mask);

            if (bits == null || wordNr >= bits.Length)
                return;

            // change the bit if needed
            if ((word & mask) > 0)
            {
                bits[wordNr] &= ~mask;
                count--;
                sequenceNr++;
            }
            else
            {
                return;
            }

            // update first and last
            if (count == 0) 
            {
                first = last = int.MinValue;
            }
            else if (count == 1)  
            {
                // was 2 items: first and last
                if (item == first)
                    first = last;
                else
                    last = first;
            }
            else // 2 or more
            {
                if (item == first)  // if the first item just been excluded
                {
                    uint w = wordNr;
                    while (bits[w] == 0)
                    {
                        w++;
                        Debug.Assert(w < bits.Length);
                    }
                    ulong fword = bits[w];
                    Debug.Assert(fword > 0);

                    uint z = 0;
                    while ((fword & 1) == 0)
                    {
                        fword >>= 1;
                        z++;
                    }

                    first = origin + (int)((w << 6) | z);
                }

                if (item == last)  // if the last item just been excluded
                {
                    uint w = wordNr;
                    while (bits[w] == 0)
                    {
                        w--;
                        Debug.Assert(w >= 0);
                    }
                    ulong lword = bits[w];
                    Debug.Assert(lword > 0);

                    uint z = 63;
                    while ((lword & 0x8000000000000000) == 0)
                    {
                        lword <<= 1;
                        z--;
                    }

                    last = origin + (int) ((w << 6) + z);
                }
            }
        }


        public void Clear()
        {
            bits = null;
            count = 0;
            first = last = int.MinValue;
            sequenceNr = 0;
        }


        internal void CalculateWordAndMask(int item, out uint wordNr, out ulong word, out ulong mask)
        {
            uint itemNr = (uint) (item - origin);
            wordNr = itemNr >> 6;
            word = (bits != null && wordNr < bits.Length) ? bits[wordNr] : 0;
            uint bitNr = itemNr & 0x3F;
            mask = 1ul << (int) bitNr;
        }


        private void ExpandBits(uint desiredSize)
        {
            uint oldSize = (uint) (bits != null ? bits.Length : 0);
            uint newSize = (desiredSize <= 2) 
                             ? desiredSize
                             : (desiredSize + 3) & ~(uint)0x3;

            ulong[] newBits = new ulong[newSize];
            if (oldSize > 0)
                Array.Copy(bits, newBits, oldSize);
            Array.Clear(newBits, (int)oldSize, (int)(newSize - oldSize));

            bits = newBits;
        }


        /// <summary>
        /// Count of items in the set.
        /// </summary>
        public int Count
        {
            get { return count; }
        }

        public bool IsEmpty
        {
            get { return count == 0; }
        }

        public bool IsNotEmpty
        {
            get { return count > 0; }
        }


        public int First
        {
            get { return first; }
        }

        public int Last
        {
            get { return last; }
        }


        public bool Contains(int item)
        {
            if (item < origin)
                return false;

            uint wordNr;
            ulong word, mask;
            CalculateWordAndMask(item, out wordNr, out word, out mask);

            return (word & mask) > 0;
        }


        public RIterator<int> TakeIterator()
        {
            return new Iterator(this);
        }


        IEnumerator<int> IEnumerable<int>.GetEnumerator()
        {
            return new Iterator(this);
        }


        IEnumerator IEnumerable.GetEnumerator()
        {
            return new Iterator(this);
        }



        internal class Iterator : RIterator<int>, IEnumerator<int>
        {
            /// <summary>
            /// Bit set which this iterator for.
            /// </summary>
            private readonly BitIntSet bitset;

            /// <summary>
            /// Number of word in bits array.
            /// </summary>
            private uint wnr;

            /// <summary>
            /// Current word.
            /// </summary>
            private ulong word;

            /// <summary>
            /// Current mask.
            /// </summary>
            private ulong mask;


            /// <summary>
            /// The current value.
            /// </summary>
            private int current;

            /// <summary>
            /// Where.
            /// </summary>
            private sbyte where;

            /// <summary>
            /// Sequence number that is assigned when this iterator was created or reset.
            /// </summary>
            private uint refSequenceNr;


            internal Iterator(BitIntSet bitset)
            {
                this.bitset = bitset;
                Reset();
            }


            private Iterator(BitIntSet bitset, int current, ulong mask, uint refSequenceNr, sbyte where, uint wnr, ulong word)
            {
                this.bitset = bitset;
                this.current = current;
                this.mask = mask;
                this.refSequenceNr = refSequenceNr;
                this.where = where;
                this.wnr = wnr;
                this.word = word;
            }


            public void Reset()
            {
                where = -1;
                refSequenceNr = bitset.sequenceNr;
                current = int.MinValue;
            }

            
            public bool Next()
            {
                if (refSequenceNr != bitset.sequenceNr)
                    throw new CollectionModifiedException();

                switch (where)
                {
                case -1:
                    if (bitset.IsNotEmpty)
                    {
                        current = bitset.First;
                        bitset.CalculateWordAndMask(current, out wnr, out word, out mask);
                        where = 0;
                        Debug.Assert((word & mask) > 0);
                    }
                    else
                    {
                        where = +1;
                    }
                    break;

                case 0:
                    Debug.Assert(mask > 0);
                    Debug.Assert(word > 0);

                    // determine whether _word_ has bits elder than _mask_
                    bool more = mask < 0x8000000000000000 && word >= (mask << 1);
                    if (more)
                    {
                        do { mask <<= 1; current++; }
                            while ( (word & mask) == 0 );
                    }
                    else if (current < bitset.Last)
                    {
                        do { wnr++; }
                            while ( bitset.bits[wnr] == 0 );
                        word = bitset.bits[wnr];
                        mask = 1;
                        current = bitset.origin + (int)(wnr << 6);
                        while ((word & mask) == 0)
                        {
                            mask <<= 1;
                            current++;
                        }
                    }
                    else
                    {
                        where = +1;
                        current = int.MinValue;
                    }
                    break;
                }

                return where == 0;
            }


            public int Current
            {
                get { return current; }
            }

            public sbyte Where
            {
                get { return where; }
            }


            public RIterator<int> Clone()
            {
                return new Iterator(bitset, current, mask, refSequenceNr, where, wnr, word);
            }


            object IEnumerator.Current
            {
                get { return Current; }
            }


            bool IEnumerator.MoveNext()
            {
                if (Where < +1)
                    return Next(); // shifts the iterator
                else
                    return false;
            }


            public void Dispose()
            {
                where = +1;
                current = int.MinValue;
            }
        }
    }


}